using System;

namespace Common.Util
{
	public class RBTree<T>  where T : IComparable 
	{
		private RBNode root = null;

		protected class RBNode
		{
			public RBNode left,right,parent;
			public bool color;
			public T value;

			public void addLeftNode(RBNode node)
			{
				this.left = node;
				if(node != null) node.parent = this;
			}

			public void addRightNode(RBNode node)
			{
				this.right = node;
				if(node != null) node.parent = this;
			}
		}
	

		protected void rotate(RBNode current,bool direction)
		{
			if (direction) {//右旋
				RBNode parent = current.parent;
				RBNode left = current.left;
				if(left == null) return;
				RBNode leftright = left.right;

				if(parent != null)//设置左节点
				{
					if(parent.left == current)
						parent.addLeftNode(left);
					else 
						parent.addRightNode(left);
				}else{//根节点
					root = left;
					left.parent = null;
				}
				left.addRightNode(current);//设置当前父节点为左节点
				current.addLeftNode(leftright);//左节点的右子节点设为当前节点的左子节点
			} else {//左旋
				RBNode parent = current.parent;
				RBNode right = current.right;
				if(right == null) return;
				RBNode rightleft = right.left;

				if(parent != null)//设置右节点
				{
					if(parent.left == current)
						parent.addLeftNode(right);
					else
						parent.addRightNode(right);
				}else{
					root = right;
					right.parent = null;
				}
				right.addLeftNode(current);//设置当前节点父节点为右子节点
				current.addRightNode(rightleft);//右节点的左子节点为当前节点的右子节点
			}
		}

		public RBTree ()
		{
		}

		public void insert(T value)
		{
			RBNode node = new RBNode ();
			node.value = value;
			node.color = true;
			RBNode current = root, parent = null;
			while (current != null) {
				parent = current;
				if(current.value.CompareTo(node.value) < 0)
					current = current.right;
				else current = current.left;
			}
			if (parent == null) {
				root = node;
			}else if (parent.value.CompareTo(value) < 0)
				parent.addRightNode (node);
			else
				parent.addLeftNode (node);


		}

		private void fixTree(RBNode node)
		{
			do{
				if (node == root) {
					node.color = false;
				} else if (node.parent.color) {
					if(node.parent.parent.left != null &&
					   node.parent.parent.right != null &&
					   node.parent.parent.left.color == node.parent.parent.right.color)
					{
						node.parent.parent.left.color= node.parent.parent.right.color = false;
						node.parent.parent.color = true;
						node = node.parent.parent;
					}
					else if(node.parent.right == node){
						this.rotate(node.parent,false);
						node = node.left;
					}else {
						this.rotate(node.parent,true);
						node.color = false;
						node.left.color = node.right.color = true;
					}
				}
			}while(node.color);
			
		}

		private void remove(T value)
		{
			RBNode current = root;
			while (current != null) {
				int result = current.value.CompareTo(value);
				if(result == 0)
				{
					break;
				}else if(result < 0)
					current = current.right;
				else
					current = current.left;
			}
		}
	}
}

